package com.shuang.graph9;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //设计输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String beginStr = sc.next();
        String endStr = sc.next();
        sc.nextLine();

        //字典集合(用Set存储 用于后续改变字符串后判断是否在字典中出现过)
        Set<String> set = new HashSet<>();

        for (int i = 0; i < n; i++) {
            set.add(sc.nextLine());
        }

        //广搜找最短路径
        int count = bfs(beginStr, endStr, set);

        System.out.println(count);
    }

    public static int bfs(String beginStr, String endStr, Set<String> set) {
        //定义map集合 key为当前字符串 值为到当前字符串时的最短路径长度
        //通过key来避免访问过的节点重复访问 值用来找最短路径
        Map<String, Integer> map = new HashMap<>();

        //定义队列
        Queue<String> que = new LinkedList<>();

        //开始节点加进去
        que.add(beginStr);

        //进行标记访问过并此时最短路径为1
        map.put(beginStr, 1);

        while (!que.isEmpty()) {
            //取出当前节点
            String curWord = que.poll();

            //得到当前节点的最短路径
            int path = map.get(curWord);

            //遍历当前节点字符串的每个字符进行替换操作 并在字典中比对有的话就路径加1 直到最后找到endStr
            for (int i = 0; i < curWord.length(); i++) {
                String newWord = curWord; //每次都要置换一个字母 所以先记录下当前字符串
                for (char j = 'a'; j <= 'z'; j++) {

                    char[] chars = newWord.toCharArray();
                    chars[i] = j;
                    String newWordStr = new String(chars);

                    if (newWordStr.equals(endStr)) {
                        //替换后与终点字符相同说明找到了最终最短路径
                        return path + 1;
                    }

                    //如果替换后遇到的是字典中的字符串并且没有被访问过
                    if (set.contains(newWordStr) && !map.containsKey(newWordStr)) {
                        que.add(newWordStr);
                        map.put(newWordStr, path + 1);
                    }
                }
            }
        }

        //没找到
        return 0;
    }
}
